package cn.edu.besti.cs1623.cw2324;
import ch16.ElementNotFoundException;
import ch16.LinkedBinaryTree;
import ch17.BSTNode;
import ch17.BinarySearchTree;

/**
 * Created by 春旺 on 2017/10/26.
 */
public class LinkedBinarySearchTree<T extends Comparable<T>>
        extends LinkedBinaryTree<T> implements BinarySearchTree<T>
{
    //-----------------------------------------------------------------
// Creates an empty binary search tree.
//-----------------------------------------------------------------
    public LinkedBinarySearchTree()
    {
        super();
    }
    //-----------------------------------------------------------------
// Creates a binary search tree with the specified element at its
// root.
//-----------------------------------------------------------------
    public LinkedBinarySearchTree(T element)
    {
        root = new BSTNode<T>(element);
    }
    //-----------------------------------------------------------------
// Adds the specified element to this binary search tree.
//-----------------------------------------------------------------
    public void add (T item)
    {
        if (root == null)
            root = new BSTNode<T>(item);
        else
            ((BSTNode)root).add(item);
    }
    //-----------------------------------------------------------------
    // Removes and returns the element matching the specified target
    // from this binary search tree. Throws an ElementNotFoundException
    // if the target is not found.
    //-----------------------------------------------------------------
    public T remove (T target) throws ElementNotFoundException {
        BSTNode<T> node = null;
        if (root != null)
            node = ((BSTNode)root).find(target);
        if (node == null)
            throw new ElementNotFoundException("Remove operation failed. "
                    + "No such element in tree.");
        root = ((BSTNode)root).remove(target);
        return node.getElement();
    }
//-----------------------------------------------------------------
// The following methods are left as programming projects.
//-----------------------------------------------------------------
 public T findMin()throws ElementNotFoundException {

        T min ;
        while (root.getLeft()!=null ){
           root = root.getLeft();

        }
        min = root.getElement();
        return min;

 }
 public T findMax()throws ElementNotFoundException {
     T max ;
     while (root.getRight()!=null ){
         root = root.getRight();
     }
     max  = root.getElement();
     return max;
 }
 public T find(T target){
        T re = null;
        if (root.find(target).getElement() == target){
            re = target;
        }
        return  re;
 }

}
